package com.shen.mianshi;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Set;
/*（一）LRU算法
	业务场景：面对大量请求时，为了减少下游系统（DB，缓存，或下游接口）压力，一般会用到LRU算法识别热点数据。请编写一个LRU算法识别热点数据，

	要求：

	（1）利用自己熟悉的数据结构编写，可以使用Map，但不能使用LinkedHashMap。

	（2）500ms内被访问3次才会认为是热点数据。

	（3）访问命中热点数据时，可以立即返回数据。

	（4）热点数据只能被缓存500ms，过期后不能再使用。

	（5）缓存容量上限是1000。
*/

/**
 * 根据要求，得出 LRU算法简易实现。
 *
 * @author luolike 尚有不足之处，希望我的大概意思已经表达清楚了。
 *
 */

public class LruAlgo {

    private int maxSize;

    //
    public static final Integer UPPER_LIMIT = 1000;

    // 访问记录超时 ：ms
    public static final Integer ALIVE_HIS = 500;

    // 热点超时：ms
    public static final Integer ALIVE_HOT = 500;

    // int[0] 记录时间戳，int[1] 记录访问次数
    private HashMap<Integer, long[]> history = new HashMap<Integer, long[]>();

    private Object lockHistory = new Object();

    private Object lockHot = new Object();

    // 线程退出条件
    private boolean falg = true;

    private HashMap<Integer, Long> hotResources = new HashMap<Integer, Long>();

    private TimeoutChecker checker;

    public LruAlgo(int maxSize) {
        // 初始化参数，容器等。
        if (maxSize > 0 && maxSize <= UPPER_LIMIT) {
            this.maxSize = maxSize;
        }
        this.checker = new TimeoutChecker();

        this.checker.run();
    }

    // 超时检查。
    private class TimeoutChecker implements Runnable {
        public void run() {
            while (falg) {
                long t0 = System.currentTimeMillis();
                // 访问记录超时。
                synchronized (lockHistory) {
                    // 访问记录超时移除。
                    Set<?> entry = history.entrySet();
                    Iterator<?> itr = entry.iterator();
                    while (itr.hasNext()) {
                        long[] val = (long[]) itr.next();
                        if (t0 - val[0] >= ALIVE_HIS) {
                            itr.remove();
                        }
                    }
                }

                // 热点超时。
                synchronized (lockHot) {
                    // 访问热点超时移除。
                    Set<?> entry = hotResources.entrySet();
                    Iterator<?> itr = entry.iterator();
                    while (itr.hasNext()) {
                        long val = (Long) itr.next();
                        if (t0 - val >= ALIVE_HOT) {
                            itr.remove();
                        }
                    }
                }
                try {
                    Thread.sleep(500);
                } catch (InterruptedException e) {
                    // ....
                    e.printStackTrace();
                }

            }

        }
    }

    // 请求方法
    public Object request(Integer resId) {
        Long t0 = System.currentTimeMillis();
        Long timeStamp = hotResources.get(resId);
        // 先判断是否存在热点。
        if (null != timeStamp) {
            // 更新热点时间戳。
            synchronized (lockHot) {
                hotResources.replace(resId, t0);
            }
            return "返回热点资源,id:" + resId;
        } else {
            // 热点不存在。
            long[] val = history.get(resId);
            if (null != val) {
                // 判断已经访问过的资源
                if (t0 - val[0] < ALIVE_HIS) {
                    if (++val[1] >= 3) {
                        synchronized (lockHot) {
                            // 访问次数超过3次判定为热点。
                            if (hotResources.size() <= maxSize) {
                                hotResources.put(resId, t0);
                            }
                        }
                    }
                }
            } else {
                synchronized (lockHistory) {
                    // 从未访问过的资源
                    history.put(resId, new long[] { t0, 1 });
                }
            }
        }
        return "返回立即资源,id:" + resId;
    }
}

